import java.util.ArrayDeque;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Queue;

/**
 * @作者 钟先崟
 * @时间 2023-03-25 18:14
 * @说明 146. LRU 缓存
 * 请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
 * 实现 LRUCache 类：
 * LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
 * int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
 * void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
 * 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
 */
public class LRUCache {
    public static void main(String[] args) {
        LRUCache lruCache1 = new LRUCache(2);
        lruCache1.put(1, 1);
        lruCache1.put(2, 2);
        lruCache1.get(1);
        lruCache1.put(3, 3);
        lruCache1.get(2);
        lruCache1.put(4, 4);
        lruCache1.get(1);
        lruCache1.get(3);
        lruCache1.get(4);
    }

    int len = 0;
    int maxLen;
    int[] keyVaule = new int[10001];
    Queue<Integer> lruCache;

    public LRUCache(int capacity) {
        maxLen = capacity;
        lruCache = new ArrayDeque<>();
    }

    public int get(int key) {
        if (keyVaule[key] != 0) {
            lruCache.remove(key);
            lruCache.add(key);
        }
        return keyVaule[key] - 1;

    }

    public void put(int key, int value) {
        if (keyVaule[key] == 0) {//不存在
            keyVaule[key] = value + 1;
            len++;
            if (len > maxLen) {//超长
                len--;
                Integer remove = lruCache.remove();
                keyVaule[remove] = 0;
            } else {//不超长
                lruCache.add(key);
            }
        } else {//存在
            lruCache.remove(key);
            lruCache.add(key);
            keyVaule[key] = value + 1;
        }
    }
}

/*
class LRUCache extends LinkedHashMap<Integer, Integer> {
    private int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
}
*/
